Given an array, rotate the array to the right by k steps, where k is non-negative.
Input: [1,2,3,4,5,6,7] and k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] rotate 3 steps to the right: [5,6,7,1,2,3,4]
Input: [-1,-100,3,99] and k = 2 Output: [3,99,-1,-100] Explanation: rotate 1 steps to the right: [99,-1,-100,3] rotate 2 steps to the right: [3,99,-1,-100]
- Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
- Could you do it in-place with O(1) extra space?
implSolution{pubfnrotate(nums:&mutVec<i32>,k:i32){for _ in0..k {for i in(1..nums.len()).rev(){ nums.swap(i, i - 1);}}}}implSolution{pubfnrotate(nums:&mutVec<i32>,k:i32){let k = k asusize % nums.len();let last_k = nums[(nums.len() - k)..].to_vec();for i in(k..nums.len()).rev(){ nums.swap(i, i - k);} nums.splice(..k, last_k);}}implSolution{pubfnrotate(nums:&mutVec<i32>,k:i32){let k = k asusize % nums.len(); nums.reverse(); nums[..k].reverse(); nums[k..].reverse();}}implSolution{pubfnrotate(nums:&mutVec<i32>,k:i32){let k = k asusize % nums.len();letmut start = 0;letmut cnt = 0;while cnt < nums.len(){letmut cur = start;letmut prev = nums[cur];loop{let next = (cur + k) % nums.len();let temp = nums[next]; nums[next] = prev; cur = next; prev = temp; cnt += 1;if start == cur {break;}} start += 1;}}}